# coding = utf-8

"""
换零钱问题，将一个整面额换成零钱，要求零钱张数最小。

采用贪心算法，每次都取最大的零钱，不满足再取小的零钱。

"""


def change(target: int, options: list):
    # 将options逆序排序
    sorted_options = sorted(options, reverse=True)
    changes = 0
    selected = []
    for o in sorted_options:
        # 每次从最大的开始叠加，直到最大的不满足才退而求其次
        while changes + o <= target:
            changes += o
            selected.append(o)
        if changes == target:
            break
    print(selected)


if __name__ == '__main__':
    change(100, [20, 10, 5, 1])
    change(6, [1, 3, 4])
    change(9, [1, 3, 4])
    change(10, [1, 3, 4])
